package main.leetcode.clockin.March;

/**
 * 994.腐烂的橘子
 *
 * <p>在给定的网格中，每个单元格可以有以下三个值之一：
 *
 * <p>值 0 代表空单元格； 值 1 代表新鲜橘子； 值 2 代表腐烂的橘子。 每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
 *
 * <p>返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
 *
 * <p>
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/rotting-oranges
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day4 {
    public static void main(String[] args) {
        System.out.println(new day4().orangesRotting(new int[][] {{1}}));
        //    System.out.println(new ex994().orangesRotting(new int[][] {{2, 1, 1}, {0, 1, 1}, {1,
        // 0,
        // 1}}));
        //    System.out.println(new ex994().orangesRotting(new int[][] {{0, 2}}));
    }

    // bfs
    //  public int orangesRotting(int[][] grid) {
    //    int m = grid.length;
    //    int n = grid[0].length;
    //    Queue<int[]> queue = new LinkedList<>(); // 记录每一轮腐烂橘子数
    //    int i, j, k;
    //    int num = 0; // num记录新鲜的桔子个数
    //    // 记录最开始的腐烂橘子的坐标 和 新鲜橘子的个数
    //    for (i = 0; i < m; i++)
    //      for (j = 0; j < n; j++) {
    //        if (grid[i][j] == 2) queue.add(new int[] {i, j});
    //        if (grid[i][j] == 1) num++;
    //      }
    //    int[] now;
    //    int size;
    //    int minutes = 0;
    //    while (num > 0 && !queue.isEmpty()) {
    //      minutes++;
    //      size = queue.size();
    //      for (k = 0; k < size; k++) { // 取出第一轮所有腐烂的橘子
    //        now = queue.remove();
    //        i = now[0];
    //        j = now[1];
    //        if (i > 0 && grid[i - 1][j] == 1) { // 上
    //          queue.add(new int[] {i - 1, j});
    //          grid[i - 1][j] = 2;
    //          num--;
    //        }
    //        if (i < m - 1 && grid[i + 1][j] == 1) { // 下
    //          queue.add(new int[] {i + 1, j});
    //          grid[i + 1][j] = 2;
    //          num--;
    //        }
    //        if (j > 0 && grid[i][j - 1] == 1) { // 左
    //          queue.add(new int[] {i, j - 1});
    //          grid[i][j - 1] = 2;
    //          num--;
    //        }
    //        if (j < n - 1 && grid[i][j + 1] == 1) { // 右
    //          queue.add(new int[] {i, j + 1});
    //          grid[i][j + 1] = 2;
    //          num--;
    //        }
    //      }
    //    }
    //    return num > 0 ? -1 : minutes;
    //  }

    private int m, n;
    // dfs
    // grid[i][j]中存放橘子的腐烂值，≥2都表示已腐烂
    // 每轮传播，腐烂橘子其四个正方向上的橘子的腐烂值都将+1
    // 腐烂值越大，表示他离初始的腐烂橘子越远，所需的传播时间越长
    // 因此，本题所需的 没有新鲜橘子为止所必须经过的最小分钟数，也就是求传染完毕后的 最大腐烂值
    public int orangesRotting(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        int i, j;
        // 开始传染
        for (i = 0; i < m; i++) for (j = 0; j < n; j++) if (grid[i][j] == 2) dfs(grid, i, j, 2);
        // 传染完毕，寻找最大腐烂值
        int max = 0;
        for (i = 0; i < m; i++)
            for (j = 0; j < n; j++) {
                if (grid[i][j] == 1) return -1;
                max = Math.max(max, grid[i][j]);
            }
        return max > 2 ? max - 2 : 0;
    }

    private void dfs(int[][] grid, int i, int j, int rotVal) {
        grid[i][j] = rotVal;
        // 传染新鲜的桔子 以及 更远的橘子
        // 但是更远的橘子他自身的腐烂值比较大时（也就是该橘子腐烂的更慢时），就需要更新他的腐烂值，说明他可以被传播的更快
        if (i > 0 && (grid[i - 1][j] == 1 || grid[i - 1][j] > rotVal + 1)) // 上
        dfs(grid, i - 1, j, rotVal + 1);
        if (i < m - 1 && (grid[i + 1][j] == 1 || grid[i + 1][j] > rotVal + 1)) // 下
        dfs(grid, i + 1, j, rotVal + 1);
        if (j > 0 && (grid[i][j - 1] == 1 || grid[i][j - 1] > rotVal + 1)) // 左
        dfs(grid, i, j - 1, rotVal + 1);
        if (j < n - 1 && (grid[i][j + 1] == 1 || grid[i][j + 1] > rotVal + 1)) // 右
        dfs(grid, i, j + 1, rotVal + 1);
    }
}
